package chart.图的存储;

import java.util.*;

/**
 * 邻接表
 * <p>相当于树的孩子表示法</p>
 * <p>适用于存储稀疏图, 边少</p>
 *
 * @author yezh
 * @date 2023/7/10 15:49
 */
public class AdjacencyTable extends AbstractGraph {

    public static void main(String[] args) {
        AdjacencyTable undirectedGraph = new AdjacencyTable(4, false);
        Edge e1 = new Edge(0, 1);
        Edge e2 = new Edge(0, 2);
        Edge e4 = new Edge(1, 2);
        Edge e3 = new Edge(1, 3);
        Edge e5 = new Edge(2, 3);
        List<Edge> edges = Arrays.asList(e1, e2, e3, e4, e5);
        undirectedGraph.createGraph(edges);
        undirectedGraph.print();
        System.out.println();
        System.out.println(undirectedGraph.getNeighborVertex(0));
        System.out.println(undirectedGraph.getNeighborVertex(1));
        System.out.println(undirectedGraph.getNeighborVertex(2));
        System.out.println(undirectedGraph.getNeighborVertex(3));
    }

    private VertexNode[] adjTable;

    public AdjacencyTable(int v, boolean directed) {
        super(v, directed);
        adjTable = new VertexNode[v];
        for (int i = 0; i < v; i++) {
            adjTable[i] = new VertexNode(i);
        }
    }

    @Override
    public void createGraph(List<Edge> edges) {
        for (Edge edge : edges) {
            addArc2Tail(edge);
        }
    }

    @Override
    public List<Integer> getNeighborVertex(int vertex) {
        // 时间复杂度: O(1)
        List<Integer> neighborVertexes = new ArrayList<>(adjTable[vertex].e);
        ArcNode cur = adjTable[vertex].firstArc;
        while (cur != null) {
            neighborVertexes.add(cur.vertex);
            cur = cur.nextArc;
        }
        return neighborVertexes;
    }

    @Override
    public List<Edge> getNeighborEdge(int vertex) {
        List<Edge> neighborVertexes = new ArrayList<>(adjTable[vertex].e);
        ArcNode cur = adjTable[vertex].firstArc;
        while (cur != null) {
            neighborVertexes.add(new Edge(vertex, cur.vertex, cur.weigh));
            cur = cur.nextArc;
        }
        return neighborVertexes;
    }

    @Override
    public List<Edge> allEdge() {
        List<Edge> edges = new ArrayList<>();
        for (VertexNode vertexNode : adjTable) {
            edges.addAll(getNeighborEdge(vertexNode.vertex));
        }
        return edges;
    }

    @Override
    public void print() {
        for (int i = 0; i < v; i++) {
            System.out.println(getNeighborVertex(i));
        }
    }

    /**
     * 尾插法
     */
    public void addArc2Tail(Edge edge) {
        VertexNode vertexNode = adjTable[edge.getArcTail()];
        ArcNode arcNode = new ArcNode(edge.getArcHead(), edge.getWeigh());
        if (vertexNode.firstArc == null) vertexNode.firstArc = arcNode;
        else {
            ArcNode cur = vertexNode.firstArc;
            while (cur.nextArc != null) cur = cur.nextArc;
            cur.nextArc = arcNode;
        }

        if (!directed) {
            vertexNode = adjTable[edge.getArcHead()];
            arcNode = new ArcNode(edge.getArcTail(), edge.getWeigh());
            if (vertexNode.firstArc == null) vertexNode.firstArc = arcNode;
            else {
                ArcNode cur = vertexNode.firstArc;
                while (cur.nextArc != null) cur = cur.nextArc;
                cur.nextArc = arcNode;
            }
        }
    }

    public static class ArcNode {
        int vertex;
        /**
         * 权重
         */
        int weigh;
        ArcNode nextArc;

        public ArcNode(int vertex, int weigh) {
            this.vertex = vertex;
            this.weigh = weigh;
            this.nextArc = null;
        }

    }

    public static class VertexNode {
        int vertex;
        ArcNode firstArc;
        /**
         * 边数
         */
        int e;

        public VertexNode(int vertex) {
            this.vertex = vertex;
            this.firstArc = null;
        }

    }

}
